package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

/**
 * 错误写法
 * @author tzp
 * @since 2020/11/4
 */
public class LC1000_1 implements DynamicProblem {

    int[] stones;
    int[][] dp;
    int K;

    public int mergeStones(int[] stones, int K) {//s=7, K=3
        this.stones = stones;
        this.K = K;
        int n = stones.length;
        if ((n - 1) % (K - 1) != 0) return -1;//不可解

        this.dp = new int[n][n];//合并i到j需要的最小分数
        for (int scale = K; scale <= n; ) {
            for (int i = 0; i + scale - 1 < n; i++) {
                if (scale == K) {//初始scale=3
                    dp[i][i + scale - 1] = sum(i, i + scale - 1);
                } else {
                    dp[i][i + scale - 1] = ditui(i, i + scale - 1, K);
                }
            }
            scale += K - 1;
        }
        return dp[0][n - 1];
    }

    //求start到end的min分数, 大概是阶乘吧
    //把start到end分成toBeSet段, 有xx种方式, 其中取个分数最小的
    public int ditui(int start, int end, int toBeSet) {
        if (toBeSet == 1) {
            return dpOrSum(start, end);
        }
        int min = Integer.MAX_VALUE;
        for (int j = start; j <= end - toBeSet + 1; ) {//1-5分成3段, j取值: 1, 2, 3
            min = Math.min(min, dpOrSum(start, j) + ditui(j + 1, end, toBeSet - 1));
            j += K - 1;
        }
        return min;
    }

    public int dpOrSum(int from, int to) {
        int dpV = dp[from][to];
        return dpV == 0 ? sum(from, to) : dpV * 2;
    }

    //both include
    public int sum(int from, int to) {
        if (from > to) return 0;
        int sum = 0;
        for (int j = from; j <= to; j++) {
            sum += stones[j];
        }
        return sum;
    }

    //helper
    public String pr() {
//        int[] a = {4, 6, 4, 7, 5};//10,
        //10,4,7,5 =10
        //10,11,5 =11
        //10,16 =16
        //26 = 26
        return null;
    }


    public static void main(String[] args) {
//        System.out.println(new LC1000_1().mergeStones(new int[]{6, 4, 4, 6, 4, 7, 9}, 4));//58
//        System.out.println(new LC1000_1().mergeStones(new int[]{3, 2, 4, 1}, 2));//20
        System.out.println(new LC1000_1().mergeStones(new int[]{4, 6, 4, 7, 5}, 2));//62
        //int[] a = {4, 6, 4, 7, 5};
        //10,4,7,5 =10
        //10,11,5 =11
        //10,16 =16
        //26 =26
        //total=63, 虽然不是最优, 但是可以看出*2那行有问题
    }
}
